home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1997 August / Walnut Creek CDROM.7z / LISTINGS / V_12_11 / ALLISON / VECTOR.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-04  |  3.6 KB  |  163 lines
  1. LISTING 27 - A Vector class template that manages its own heap
  2. #include <iostream.h>
  3. #include <stddef.h>
  4. #include <stdlib.h>
  5. #include <new.h>
  6.  
  7. // Borland's <new.h> doesn't supply this:
  8. inline void *operator new(size_t, void *p)
  9. {
  10.     return p;
  11. }
  12.  
  13. // The next two are just for tracing execution:
  14. inline void *operator new(size_t siz)
  15. {
  16.     cout << ">>> operator new (" << siz << " bytes)" << endl;
  17.     return malloc(siz);
  18. }
  19.  
  20. inline void operator delete(void *p)
  21. {
  22.     cout << ">>> operator delete: " << (void *) p << endl;
  23.     free(p);
  24. }
  25.  
  26. template<class T>
  27. class Vector
  28. {
  29. public:
  30.     Vector();
  31.     Vector(size_t);
  32.     ~Vector();
  33.  
  34.     // Append & subscript:
  35.     Vector<T>& operator+=(const T&);
  36.     T& operator[](size_t);
  37.  
  38.     // Length-related functions:
  39.     size_t length() const;
  40.     void resize(size_t);
  41.     size_t capacity() const;
  42.     void reserve(size_t);
  43.  
  44. private:
  45.     T *arena;       // class-specific storage arena
  46.     size_t length_;
  47.     size_t capacity_;
  48.  
  49.     enum {CHUNK = 10};
  50.  
  51.     // Disallow copy and assign:
  52.     Vector(const Vector&);
  53.     Vector<T>& operator=(const Vector<T>&);
  54.  
  55.     static size_t next_chunk(size_t n);
  56. };
  57.  
  58. template<class T>
  59. inline Vector<T>::Vector()
  60. {
  61.     // Intialize an empty vector
  62.     arena = 0;
  63.     length_ = capacity_ = 0;
  64. }
  65.  
  66. template<class T>
  67. inline Vector<T>::Vector(size_t n)
  68. {
  69.     // Allocate a multiple of CHUNK elements >= n
  70.     length_ = 0;
  71.     capacity_ = next_chunk(n);
  72.     arena = (T *) ::operator new(sizeof(T) * capacity_);
  73.     cout << ">>> arena created at " << (void *) arena << endl;
  74. }
  75.  
  76. template<class T>
  77. Vector<T>::~Vector()
  78. {
  79.     // Execute destructor for each element
  80.     for (int i = 0; i < length_; ++i)
  81.         (arena+i)->T::~T();
  82.  
  83.     ::operator delete(arena);
  84. }
  85.  
  86. template<class T>
  87. inline T& Vector<T>::operator[](size_t pos)
  88. {
  89.     if (pos >= length_)
  90.         throw "bad index in Vector<T>::operator[]";
  91.     return arena[pos];
  92. }
  93.  
  94. template<class T>
  95. inline size_t Vector<T>::length() const
  96. {
  97.     return length_;
  98. }
  99.  
  100. template<class T>
  101. inline size_t Vector<T>::capacity() const
  102. {
  103.     return capacity_;
  104. }
  105.  
  106. template<class T>
  107. void Vector<T>::reserve(size_t new_capacity)
  108. {
  109.     // Only allow an increase:
  110.     if (new_capacity > capacity_)
  111.     {
  112.         new_capacity = next_chunk(new_capacity);
  113.         if (new_capacity > capacity_)
  114.         {
  115.             // Copy elements to new space
  116.             T *new_arena = (T*) ::operator new(sizeof(T) *
  117.                                               new_capacity);
  118.             cout << ">>> new arena created at "
  119.                  << (void *) new_arena << endl;
  120.             for (int i = 0; i < length_; ++i)
  121.                 (void) new (new_arena + i) T(arena[i]);
  122.  
  123.             // Destroy old vector
  124.             for (i = 0; i < length_; ++i)
  125.                 (arena+i)->T::~T();
  126.             delete arena;
  127.  
  128.             // Update state
  129.             arena = new_arena;
  130.             capacity_ = new_capacity;
  131.         }
  132.     }
  133. }
  134.  
  135. template<class T>
  136. void Vector<T>::resize(size_t new_length)
  137. {
  138.     // Only allow a decrease:
  139.     if (new_length < length_)
  140.     {
  141.         // Just destroy truncated elements;
  142.         // Don't change capacity
  143.         for (int i = new_length; i < length_; ++i)
  144.             (arena+i)->T::~T();
  145.         length_ = new_length;
  146.     }
  147. }
  148.  
  149. template<class T>
  150. Vector<T>& Vector<T>::operator+=(const T& x)
  151. {
  152.     if (length_ == capacity_)
  153.         reserve(length_ + 1);
  154.     (void) new (arena + length_++) T(x);
  155.     return *this;
  156. }
  157.  
  158. template<class T>
  159. inline size_t Vector<T>::next_chunk(size_t n)
  160. {
  161.     return ((n + CHUNK - 1) / CHUNK) * CHUNK;
  162. }
  163.